package com.github.yangyishe.p300;

import java.util.ArrayList;
import java.util.Collections;


/**
 * 295. 数据流的中位数
 * https://leetcode.cn/problems/find-median-from-data-stream/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
 *
 * 例如 arr = [2,3,4] 的中位数是 3 。
 * 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
 * 实现 MedianFinder 类:
 *
 * MedianFinder() 初始化 MedianFinder 对象。
 *
 * void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
 *
 * double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
 *
 * 示例 1：
 *
 * 输入
 * ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
 * [[], [1], [2], [], [3], []]
 * 输出
 * [null, null, null, 1.5, null, 2.0]
 *
 * 解释
 * MedianFinder medianFinder = new MedianFinder();
 * medianFinder.addNum(1);    // arr = [1]
 * medianFinder.addNum(2);    // arr = [1, 2]
 * medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
 * medianFinder.addNum(3);    // arr[1, 2, 3]
 * medianFinder.findMedian(); // return 2.0
 * 提示:
 *
 * -105 <= num <= 105
 * 在调用 findMedian 之前，数据结构中至少有一个元素
 * 最多 5 * 104 次调用 addNum 和 findMedian
 */
public class Problem295 {
    public static void main(String[] args) {
         MedianFinder medianFinder = new MedianFinder();
         medianFinder.addNum(1);    // arr = [1]
         medianFinder.addNum(2);    // arr = [1, 2]
        System.out.println("medianFinder.findMedian() = " + medianFinder.findMedian()); // 返回 1.5 ((1 + 2) / 2)
         medianFinder.addNum(3);    // arr[1, 2, 3]
        System.out.println("medianFinder.findMedian() = " + medianFinder.findMedian()); // return 2.0
    }


}

/**
 * 思路:
 * 考虑使用堆实现.
 * 当size>3时, 维护一个size/2的大顶堆, 以及相同大小的小顶堆, 以及一个中间元素(可能为空)
 * 维护一个逻辑树, 树的左侧是小于顶部元素的大顶堆; 树的右侧是大于顶部元素的小顶堆.
 * 两个堆的大小总是一致的.
 * 如果元素总数量为奇数, 则堆顶元素就是中间数; 如果元素总数量为偶数, 则堆顶元素为空, 中间值为两个堆的堆顶的元素的平均值.
 * 堆本身使用ArrayList实现, 底层为数组, 同时可以自动扩容.
 *
 * 当增加元素时,
 * 如果原来元素数量为偶数, 则分别与左侧堆顶元素和右侧堆顶元素比较, 如果恰好处于两个元素中间(含相等), 就放在中间元素; 否则就把要替代的元素放在中间, 同时原来的堆顶元素放上新的元素, 再维护堆化
 * 如果原来元素数量是奇数, 则与中间元素比较, 判断该元素应该放在左侧还是右侧, 如果放在右侧, 则将该元素放在右侧小顶堆末尾, 再堆化, 同时将原来的中间元素放在左侧末尾, 再堆化
 *
 */
class MedianFinder {
    private Integer middle;
    private ArrayList<Integer> leftBigHeap=new ArrayList<>();
    private ArrayList<Integer> rightSmallHeap=new ArrayList<>();
    private int size=0;


    public MedianFinder() {

    }

    public void addNum(int num) {
        if(size%2==0){
            addNumWhenEven(num);
        }else{
            addNumWhenOdd(num);
        }

    }

    private void addNumWhenOdd(int num) {
        size++;
//        if(size++==1){
//            if(middle>=num){
//                leftBigHeap.add(num);
//                rightSmallHeap.add(middle);
//            }else{
//                leftBigHeap.add(middle);
//                rightSmallHeap.add(num);
//            }
//            middle=null;
//
//            return;
//        }
        if(middle>=num){
            leftBigHeap.add(num);
            rightSmallHeap.add(middle);
        }else{
            leftBigHeap.add(middle);
            rightSmallHeap.add(num);
        }
        siftUp(leftBigHeap,leftBigHeap.size()-1,true);
        siftUp(rightSmallHeap,rightSmallHeap.size()-1,false);

        middle=null;
    }



    private void addNumWhenEven(int num) {
        if(size++==0){
            middle=num;
            return;
        }
        boolean gtSmall = leftBigHeap.get(0) <= num;
        boolean ltBig = rightSmallHeap.get(0) >= num;
        if(gtSmall&&ltBig){
            middle=num;
            return;
        }
        if(!gtSmall){
            middle=leftBigHeap.get(0);
            leftBigHeap.set(0,num);
            siftDown(leftBigHeap,0,true);
        }else{
            middle=rightSmallHeap.get(0);
            rightSmallHeap.set(0,num);
            siftDown(rightSmallHeap,0,false);
        }
    }

    private void siftUp(ArrayList<Integer> heap, int i, boolean isBig) {
        while(true){
            int parent=(i-1)/2;
            if(parent<0){
                return;
            }
            if(isBig){
                if(heap.get(parent)>=heap.get(i)){
                    return;
                }
            }else{
                if(heap.get(parent)<=heap.get(i)){
                    return;
                }
            }
            Collections.swap(heap,i,parent);
            i=parent;
        }

    }

    private void siftDown(ArrayList<Integer> heap, int i,boolean isBig) {
        while(true){
            int left=i*2+1;
            int right=i*2+2;
            if(left>=heap.size()){
                return;
            }
            // 待cas的子元素索引
            int childBot;
            if(right>=heap.size()){
                childBot=left;
            }else{
                if(isBig){
                    childBot=heap.get(left)>=heap.get(right)?left:right;
                }else{
                    childBot=heap.get(left)<=heap.get(right)?left:right;
                }
            }
            if(isBig){
                if(heap.get(i)>=heap.get(childBot)){
                    return;
                }
            }else{
                if(heap.get(i)<=heap.get(childBot)){
                    return;
                }
            }
            Collections.swap(heap,i,childBot);
            i=childBot;
        }
    }

    public double findMedian() {
        if(size%2==0){
            return ((double)(leftBigHeap.get(0)+rightSmallHeap.get(0)))/2;
        }else{
            return middle;
        }
    }
}
